1990. aastateks oli selge, et hoida korras avariiolukorda sattunud Magdaleena tänava hoonet, mis polnud isegi Eesti Juudiusu Koguduse kinnisvara, on ülemäära kulukas ning perspektiivitu. Oli ka selge, et sünagoogi kolimine Magdaleena tänava puithoonest Juudi Kooli juurdeehituse ruumides asuva Juudi Kogukonna Keskuse teisele korrusele Karu tänav 16 oli algusest peale ajutine lahendus. Loota võis vaid Karu ja Aedvilja tänava ristmikul asuvale kinnistule, mis oli kogudusele tagastatud.
Kogukonna Keskuse teisel korrusel asuval sünagoogil oli mitmeid olulisi puudusi. Ruumid olid seal väikesed, mistõttu pühade ajal olid need puupüsti rahvast täis. See tõi kaasa mitmeid ebamugavusi, muu hulgas polnud võimalik kindlustada meeste ja naiste eraldatust palvetamise ajal. Peamiseks reeglitest üleastumiseks oli aga asjaolu, et polnud tagatud aron kodeš’i õige suund Jeruusalemma suhtes. Täisnurkne ja kitsas ruum võimaldas asetada selle ainult idaseina äärde, mistõttu näoga Jeruusalemma suunas lausutavate palvete ajal oli kogudus sunnitud pöörama aron kodeš’i poole küljega. Probleemiks oli seegi, et Tallinnas puudus rituaalne bassein mikve ja koššerköök. Kuna Tallinn on suur turismikeskus, esines tõsiseid probleeme Tallinna külastavate juudi turistide vajaduste täitmisega.
Juba 1990. aastate keskel arutati võimaluse üle ehitada uus sünagoog Aedvilja tänava ääres asuvale vabale krundile, kuid tegelikke samme hakati astuma alles pärast seda, kui Tallinna oli saabunud rabi Shmuel Kot.
2006. aastal tähistati Tallinnas Maakri tänaval asunud Suure Koraalse sünagoogi ehitamise lõpetamise 120. aastapäeva. Suure sünagoogi juubeli ettevalmistamise käigus selgines ka uue sünagoogi ehitamise idee. Otsustati, et sellest peab kujunema tõeline juudielu keskus. Kavandati, et sünagoogist saab koht, kus mitte ainult ei palvetata, vaid seal saavad olema mikve, koššerrestoran, kultuurikeskus ja muuseum. Kogudus vajas ka sobilikke haldusruume. Eesti Juudiusu Kogukonna esimees Boris Oks, kes nooruses oli konstrueerimisinsener ja seejärel aastakümneid ettevõtte Leek direktor, koostas aastatel 2003–2004 koos rabi Shmuel Kotiga Juudi Kogukonna Keskuse Aedvilja tänava poolse neljakorruselise juurdeehituse orienteeruva projekti ja kuluarvutuse. Esimene tegelik samm sünagoogi ehitusplaanide realiseerimise suunas oli 2. juulil 2004. aastal ettevõtja Vladimir Libmani kabinetis peetud nõupidamine, kus osalesid Fjodor Berman, Shmuel Kot, Boris Oks, Mark Šagal, Armin Kulman, Mihhail Daškovski, Aleksandr Halemski, Aleksandr Burõhh, Mark Eivin ja Leonid Eivin. Nõupidamisel rõhutati, et Juudi Kogukonna Keskuse teisel korrusel asuva sünagoogi tegutsemise teevad keeruliseks ühine sissekäik kooliga, laste klasside töö kolmandal korrusel, Juudi Kogukonna Sotsiaalkeskust külastavate inimeste suur arv ja väliste eritunnuste puudumine hoonel, kus viiakse läbi teenistusi. Samuti mainiti, et Eesti Juudiusu Kogudusel puuduvad haldusruumid ja ruumid, kus pidada pulmi, täisealiseks saamise ehk bar mitsva ja bat mitsva tähistamisi ning korraldada teisi pidustusi, sündmusi ja üritusi. Pole püsivat hoonet koššertoodete valmistamiseks ja müümiseks, puudub rituaalse puhastuse bassein mikve. Peeti mõistlikuks, et uue hoone fassaad oleks Tallinna Maakri tänava Suure sünagoogi täpne koopia.
Sel hetkel hinnati rekonstrueerimise ja ehituskulude suuruseks 6,5 miljonit Eesti krooni. 2004. aasta juulikuuks saabusid vastused võimalikelt sponsoritelt Ameerika Ühendriikidest. George Rohri Perekonna Fond nõustus eraldama 350 000 dollarit, mis pidi katma 60 protsenti kuludest. Koosolekust osavõtjad rõhutasid, et oleks ebaõige ehitada sünagoog ainuüksi Ameerika juutide rahaga. Märtsis 2004 saadetigi toetusetaotlus ka Venemaa pearabi Berl Lazarile. Eesti juutkonna annetuste kogumiseks otsustati Eesti Juudiusu Koguduse juurde luua Sihtasutus „Sünagoogi 120. aastapäev”. Sihtasutuse juhatusse valiti Boris Oks (esimees), Shmuel Kot ja Vladimir Libman.
2004. aasta lõpus eraldas George Rohr 40 000 USA dollarit arhitektuuriprojekti koostamiseks ning 5. mail 2005 sõlmisid Eesti Juudiusu Kogudus ja George Rohr lepingu rahalise abi osutamiseks Tallinna sünagoogi ehitamisel. George Rohr kohustus annetama oma perekonnaga 400 000 dollarit. Kuna idee hakkas omandama reaalseid piirjooni, ilmnes vajadus laiendada sihtasutuse juhatuse koosseisu. 9. detsembril 2004 kutsuti juhatusse täiendavalt Juri Rapoport, Cilja Laud, Eri Klas ja Mark Eivin. Aastatel 2004–2006 peeti enam kui 16 juhatuse koosolekut, kus arutati projekteerimistööde, ehituse ja rahastamisega seotud küsimusi.
Esimesel etapil toetasid ehitust rahaliselt nimekad Eesti ärimehed – Fjodor Berman, Vladimir Libman, Mark Rivkin. Annetusi tegid paljud Eesti organisatsioonid, Tallinna linnavalitsus, Eesti siseministeerium, eraisikud ning ka poliitikud, nagu näiteks Edgar Savisaar ja Andrus Ansip. Aastal 2005 liitus ehituse toetajatega Aleksander Bronštein, kes sai ehituse peasponsoriks, annetades enam kui miljon eurot. Aleksander Bronšteini palvel on Tallinna Uus sünagoog pühendatud tema 16. novembril 2004 surnud ema Beila Barski mälestusele (olgu õnnistatud tema mäletus). 2004. aasta teisel poolel korraldati konkurss projekteerimisfirma leidmiseks. Koguduse juhatus tunnistas konkursi võitjaks arhitektuuribüroo Kõresaar & Kotov (KOKO). 16. septembril 2004 sõlmiti arhitektidega leping. Noored Eesti arhitektid asusid entusiastlikult kindlaksmääratud ülesande kallale. Suure sünagoogi fassaadi taastamise ideest tuli loobuda juba projekteerimise varases faasis Tallinna peaarhitekti nõudmisel. Arhitektid pidid leidma lahenduse, mis arvestaks Eesti juutkonna kordumatust, ühendaks endas juutkonna ajaloos eksisteerinud kultuurilised eripärad ja peegeldaks kogukonna soovi taastada sünagoog Tallinnas. Projekteerimistööd viidi läbi tihedas koostöös Eesti Juudiusu Kogudusega, keda esindas Boris Oks. Kui esialgu oli kavas laiendada olemasolevat hoonet, lisades sellele esindusliku sissekäigu, raamatukogu ja tööruumid, siis varsti selgus, et tuleb mõelda uue hoone ehitamisele. Kuna KOKO arhitektidel olid üsna pealiskaudsed teadmised juudi kultuurist ja arhitektuurist, otsustati külastada juudi kultuuri ja traditsioonide allikat – Iisraeli. Eestist emigreerunud Iisraeli arhitektist Harri Sheinist sai reisijuht, kes selgitas projekteerijate rühma juhile Andrus Kõresaarele ja tema kolleegidele juudi rahva ajalugu ning tutvustas sünagoogiarhitektuuri. Arhitektidele anti täielik loominguline vabadus. Uurides erinevaid lahendusvariante, lähtusid arhitektid asjaolust, et ruum peaks justkui pöörlema inimese ümber, luues positiivse varjundi nii usutalituste kui pühade ja igapäevaste sündmuste jaoks. Iga ruum peaks justkui voolama järgmisse, nii et liikudes ei kaotaks inimene huvi ümbritseva vastu. Peale selle pidid nad sünagoogi interjööri osas järgima rangeid reegelid, mis näevad ette eraldi ruumid meestele ja naistele, määravad saali suuna ja aron kodeš’i asukoha.
Sünagoogi arhitektuuri aluseks on hoone telg. Kuna peasaal peab olema suunatud Jeruusalemma poole, on hoone telg põhja-lõuna suunaline – Karu tänava peasissekäigust kuni klaasist lõunaseinani, mille ees asetseb aron kodeš. Hoone arhitektuuriline lahendus rajaneb kahel põhimõttel. Esiteks võlvkaared, mis rõhutavad hoone sakraalset olemust. Katus ja seinad on kaetud tumedate sarlakpunaste keraamiliste plaatidega, mis rõhutavad põhikonstruktsiooni tugevust. Teiseks – hoone põhiosa toetavad sambad, mis asetsevad otsekui lainetena piki külgseinu. Sammaste vahed on kaetud klaasiga. See loob mulje, nagu hõljuks hoone massiivne karkass õhus.
Lisaks juudi traditsioonidesse ja sakraalsesse arhitektuuri sukeldumisele omandasid arhitektid ka juudi organisatsiooniga suhtlemise kogemuse. Projekti esitlus kogukonnale möödus tormakalt ja emotsionaalselt, kuid nii KOKO esindajate kui ka Boris Oksa üllatuseks sai arhitektuuriliselt ebakonventsionaalne hoone peaaegu üksmeelse toetuse. Projekteerimise ajal pidasid peasponsor Aleksander Bronštein ja rabi Shmuel Kot läbirääkimisi Venemaa pearabi Berl Lazariga. Tõeliseks proovikiviks asjaosalistele oli mikve ehitamine. Mis puudutab sisu ja ruumilist lahendust, siis enam kui saja aasta jooksul polnud midagi sellist Eestis projekteeritud. Korduvalt peeti aru spetsialisti, Ameerika Ühendriikide rabi Gershon Grossbaumiga. Riia sünagoogi rabi kutsel uuriti sealse mikve ehitust Riias.
Arhitektid ise arvavad, et pingelistel hetkedel päästis neid jäljendamatu juudi huumor ning võimalus saada niisuguse ainulaadse hoone arhitektideks, tutvudes tänu sellele ka juudi kultuuri ja uute inimestega, mida nad peavad enda jaoks teatud preemiaks. Projektis osalesid KOKO büroost Andrus Kõresaar (töörühma juht), arhitektid Kaur Stöör ja Tõnis Kimmel, sisearhitektid Liis Lindvere ja Raili Paling, ehitaja Toomas Tammerk, graafiline kujundaja Martin Lazarev ning projektijuht Jaanus Männik. Ventilatsiooni, veevarustuse ja kanalisatsiooni eriprojektid teostasid Teet Tark, Albert Rodin ja Kaia Hannus firmast Hevac, elektrivarustuse osa – Jaan Puss (Contactus), mikve – Priit Nõmmeots koos rabi Gershon Grossbaumiga. Pärast projekti valmimist hinnati sünagoogi ehituskuludeks 22 miljonit krooni. Peatöövõtja valimiseks korraldati konkurss. 1. juunil 2005 kinnitati Eesti Juudiusu Koguduse juhatuse otsusega konkursi võitjaks ehitusfirma AS Kolle, juhatuse esimees Igor Geller. 1998. aastal asutatud AS Kolle on nimekas ehitusfirma, kel on kogemusi mitmesuguste objektide ehitamisel ja kes omab 2005. aastast rahvusvahelise standardi ISO 9001:2000 kvaliteedijuhtimissüsteemi vastavussertifikaati. Firma tegevus on kandunud väljapoole Eesti piire, selle filiaalid tegutsevad Lätis, Ukrainas ja Venemaal. Tallinna Uus sünagoog oli ainulaadne ja keeruline objekt mitte ainult projekteerijatele, vaid ka ehitajatele. Nagu arhitektid, nii pidid ka ehitajad süvenema kõikidesse peensustesse, mis kerkisid esile sakraalehitise püstitamisel, ning õppima tundma juudi traditsioone. Tööd teostati arhitektide, koguduse esimehe Boris Oksa ja Eesti pearabi Shmuel Koti pideva järelevalve all. Mikve vastavust kõikidele juudi seaduse halahha nõuetele kinnitas ja andis loa selle kasutamiseks Londoni Rabiliku Kohtu (beit din) kohtunik (dajan), rabi Levi Y. Raskin. Köök on varustatud nüüdisaegsete seadmetega koššertoidu valmistamiseks. Hea akustika tagamiseks on 61 protsenti sünagoogi peasaali laepinnast kaetud erilise akustilise kipskrohviga. Lisaks paigaldati laes olevatele võlvkaartele erilised heli peegeldavad klaaskiust katted. Seetõttu saavutati saali head akustilised omadused üsna laias heliulatuses. Akustikat on kontrollitud spetsiaalsete arvutiprogrammidega.
Sünagoogi ruumide kogupind on 975 ja peasaali pindala 106,6 ruutmeetrit. Ehitust juhtisid otseselt ehitusdirektor Dmitri Rosenblat, kommertsdirektor Grigori Roiz ja projektijuht Maksin Blitštein. Tänu Aleksander Bronšteini, George Rohri perekonna ja kõikide teiste jõukohastele annetustele on saanud võimalikuks ehitada ainulaadse välimusega ja suurepärane Tallinna Uus sünagoog. Eesti juudid mäletavad nende inimeste suuremeelsust igavesti.